V parih nad sezname in nize

Vsote podseznamov

1. podnaloga

Vsote peterk

Podan je seznam nenegativnih števil in naloga je poiskati največjo vsoto petih zaporednih števil v tem seznamu. Napiši funkcijo vsota_peterk(sez), ki prejme seznam nenegativnih števil sez in vrne največjo vsoto. Če je v seznamu manj kot 5 štervil, vrni -1.

Primer (največja vsota je pri 3, 8, 9, 0, 4):

 >>> vsota_peterk([9, 1, 2, 3, 8, 9, 0, 4, 3, 7])
 24

Uradna rešitev

def vsota_peterk(sez):
    '''Vrne maksimalno vsoto pet zaporednih elementiov seznama'''
    if len(sez) < 5:
        return -1
    najvecja = 0 # doslej največja vsota
    for zacetek in range(len(sez) - 4):             # preverjamo samo do 5. elementa na koncu
        vsota = sum(sez[zacetek : zacetek + 5])     # sestevamo po 5 elementov naenkrat
        if vsota > najvecja:        # ce je trenutna vsota vecja od najvecje
            najvecja = vsota        # smo nasli novo najvecjo vsoto
    return najvecja

2. podnaloga

Sestavi funkcijo, ki za dani seznam in naravno število k izračuna in vrne seznam vsot vseh strnjenih podseznamov dolžine k.

 >>> vsote([1, 2, 3, 4], 2)
 [3, 5, 7]
 >>> vsote([2, 6, 3, 7, 5, 2, 3], 3)
 [11, 16, 15, 14, 10]
 >>> vsote([3, 5, 1], 1)
 [3, 5, 1]
 >>> vsote([3, 5, 1], 3)
 [9]
 >>> vsote([3, 5, 1], 4)
 []

Uradna rešitev

def vsote(sez, k):
    '''vsote vseh strnjenih podseznamov dolžine k'''
    if k > len(sez): #nimamo nobenega takega podseznama
        return []
    vsota = 0
    #najprej seštejemo prvih k
    for i in range(k):
        vsota += sez[i]
    sezVsot = [vsota]
    #sedaj pa gremo do konca seznama in prištejemo konec in odštejemo začetek
    for i in range(k, len(sez)):
        vsota = vsota - sez[i-k] + sez[i]
        sezVsot.append(vsota)
    return sezVsot

3. podnaloga

Razmisli, kako bi rešil nalogo, kjer moramo poiskati največjo vsoto strnjenega podzaporedja, če je seznam zelo velik (> 100 000) in iščemo največjo vsoto daljših (> 10 000) zaporedij števil. Napiši funkcijo max_vsota_nterk(s, n), kjer je s seznam števil in n število zaporednih števil.

Če bi morali poiskati vsoto desettisočerk, bi moral na vsakem koraku sešteti 10 000 števil, to bi storili skoraj milijonkrat. Vsega skupaj bi seštel deset milijard števil, za kar bi potrebovali kar nekaj časa.

Pri preverjanju na sistemu Tomo - če odgovora ne dobiš v recimo 20 sekundah - s CTRL-Cprekini program, saj tvoja rešitev očitno ni dovolj hitra!

Uradna rešitev

def max_vsota_nterk(s, n):
    '''Računanje naj n-terke v velikih seznamih'''
    najvecja = vsota = sum(s[:n]) # začetni kandidat je vsota prvih n
    for i in range(n, len(s)):          # sestevamo ze sproti
        vsota += s[i] - s[i-n]          # vsakic ko povecamo indeks za 1, se
        if vsota > najvecja:            # prvi element odsteje, naslednji pa doda
            najvecja = vsota
            
    return najvecja

Ujemanja

1. podnaloga

Sestavite funkcijo zacetek(a, b), ki bo za niza a in b preštela, v koliko začetnih znakih se ujemata.

Niza nimata nujno enakega začetka, lahko se delno ujemata na začetku, lahko se en niz v celoti pojavi na začetku drugega, ali pa sta niza celo enaka. Ni potrebno obravnavati vsakega od teh primerov posebej, samo pazite, da bo funkcija delala pravilno za vse primere.

>>> zacetek('matematika', 'fizika')
0
>>> zacetek('matematika', 'matija')
3
>>> zacetek('oder', 'oderuh')
4
>>> zacetek('izpit', 'izpit')
5

Pri rešitvi obvezno uporabite zanko while.

Uradna rešitev

def zacetek(a, b):
    ''' v koliko začetnih znakih se ujemata niza a in b'''
    i = 0
    dolžinaKrajšega = min(len(a), len(b))
    while i < dolžinaKrajšega and a[i] == b[i]:
        i += 1
    return i

2. podnaloga

Sestavite funkcijo zacetekFor(a, b), ki bo za niza a in b preštela, v koliko začetnih znakih se ujemata.

Pri rešitvi ne smete uporabiti zanke while.

Uradna rešitev

def zacetekFor(a, b):
    ''' v koliko začetnih znakih se ujemata niza a in b'''
    najkrajsi = min(len(a),len(b))
    for i in range(najkrajsi): # ustaviti se moramo, ko krajšega niza zmanjka
        if a[i] != b[i]:
            return i # i-ti znak je prvi neujemajoči, ker štejemo od 0 dalje ...
    return najkrajsi # ujemala sta se v vseh

3. podnaloga

Napiši funkcijo st_ujemanj(b1, b2), ki prejme dve besedi in vrne število znakov, v katerih se besedi ujemata.

Primeri:

>>> st_ujemanj("ROKA", "ROKAV")
4
>>> st_ujemanj("CELINKE", "POLOVINKE")
1

Uradna rešitev

def st_ujemanj(b1, b2):
    '''Koliko istoležnih znakov je enakih'''
    ujemanja = 0   
    for i in range(min(len(b1), len(b2))):  # zanka se izvede tolikokrat koliko je dolga najkrajsa beseda b1 oz. b2
        if b1[i] == b2[i]:          # ce sta znaka v obeh besedah enaka, se ujemanje poveca za 1. 
            ujemanja += 1
    return ujemanja

4. podnaloga

Napiši funkcijo ujeme(b1, b2), ki kot vhod prejme dve besedi b1 in b2, ter vrne novo besedo, ki vsebuje tiste znake, v katerih se besedi ujemata (imata na istem mestu isti znak), znaki na ostalih mestih pa so zamenjane s pikami. Če besedi nista enako dolgi, naj bo nova beseda toliko dolga, kolikor je dolga krajša izmed podanih besed.

Primeri:

>>> ujeme("ROKA", "REKE")
'R.K.'
>>> ujeme("ROKA", "ROKAV")
'ROKA'

Uradna rešitev

def ujeme(b1, b2):
    '''Vrne niz, ki označuje, kako se ujkemata niza'''
    rezultat = ""
    for i in range(min(len(b1), len(b2))):
        if b1[i] == b2[i]:      # ce sta znaka enaka
            rezultat += b1[i]   # potem v rezultat dodamo ta znak
        else:
            rezultat += "."     # sicer dodamo piko.
    return rezultat

Žaba

Žaba (Salientia) skače po ravnini. Na začetku in po vsakem skoku zabeležimo projekcijo točke (tj. položaja žabe) na abscisno in ordinatno os, s čemer dobimo seznama px in py. Sestavili bomo sklop funkcij, s katerimi bomo analizirali žabino gibanje.

1. podnaloga

Sestavite funkcijo vPravokotniku(tocka, pravokotnik), ki za dano točko tocka vrne True, če je točka znotraj ali na robu pravokotnika pravokotnik. Točka v ravnini je podana s seznamom $[x, y]$, pravokotnik pa s seznamom $[x1, y1, x2, y2]$, kjer sta $(x1, y1)$ in $(x2, y2)$ koordinati nasprotnih oglišč.

Uradna rešitev

def vPravokotniku(tocka, pravokotnik):
    [x, y] = tocka
    [x1, y1, x2, y2] = pravokotnik
    (x1, x2) = (min(x1, x2), max(x1, x2))
    (y1, y2) = (min(y1, y2), max(y1, y2))
    return x1 <= x and x <= x2 and y1 <= y and y <= y2

2. podnaloga

Sestavite funkcijo pot(px, py), ki iz danih seznamov px in py rekonstruira pot žabe, tj. vrne seznam točk, v katerih je bila žaba. Točko podano kot seznam dolžine 2.

>>> pot([0, 0, 1, 2], [0, 1, 2, 1]))
[[0, 0], [0, 1], [1, 2], [2, 1]]

Predpostavite lahko, da sta seznama px in py enakih dolžin.

Uradna rešitev

def pot(px, py):
    '''Določi točke na žabini poti'''
    kje = 0
    seznam = []
    while kje < len(px):
        seznam.append([px[kje], py[kje]])
        kje += 1
    return seznam      

##dodatno znanje nam da enovrstični zapis:
##
##def pot(px, py):
##    return [[x, y] for x, y in zip(px, py)]

3. podnaloga

Sestavite funkcijo najdaljsiSkok(tocke), ki iz seznama tocke, v katerih so zapisane točke, po katerih je skakala žaba, izračuna dolžino najdaljšega skoka. Če žaba ni naredila nobenega skoka, naj funkcija vrne None.

Uradna rešitev

def d(a, b):
    '''Razdalja med točkama a in b'''
    return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5

def najdaljsiSkok(tocke):
    '''Kako dolg je najdaljši skok'''
    if len(tocke) <= 1:
        return None
    najSkok = -1
    doskok = 1 # indeks, kjer je žaba doskočila
    while doskok < len(tocke):
        skok = d(tocke[doskok], tocke[doskok - 1])
        if skok > najSkok: # je skok daljši?
            najSkok = skok
        doskok += 1
    return najSkok    
    
##dodatno znanje nam da krajši zapis:
##def najdaljsiSkok(tocke):
##    if len(tocke) <= 1:
##        return None
##    else:
##        return max([d(tocke[i], tocke[i - 1]) for i in range(1, len(tocke))])

4. podnaloga

Žaba skače po ravnini in po nekaj skokih skoči v pravokotno blatno mlako. Sestavite funkcijo vMlaki(tocke, mlaka), ki naj vrne prvi podseznam skokov, ki v celoti potekajo po mlaki. Pri tem so skoki podani s seznamom vmesnih točk tocke, pravokotna mlaka pa s četverico mlaka, ki je oblike [x1, y1, x2, y2] kot v prvi podnalogi.

Če takega podseznama ni, naj funkcija vrne None.

Uradna rešitev

def vMlaki(tocke, mlaka):
    '''Vrne prvi seznam skokov, ki potekajo po mlaki'''
    podSeznam = None
    katera = 0
    while katera < len(tocke):
        tocka = tocke[katera]
        if vPravokotniku(tocka, mlaka): # če smo v mlaki 
            if podSeznam == None: # še nimamo podseznama
                podSeznam = [tocka]
            else:
                podSeznam.append(tocka)
        elif podSeznam == None: # če nismo v mlaki in
                                # sploh še nismo skočili v mlako
            katera += 1
            continue # skačemo naprej
        else:
            break # konec veselja, bili smo v mlaki in smo skočili ven
        katera += 1
    return podSeznam

Igra življenja

Igro življenja si je izmislil britanski matematik John H. Conway, gre pa takole: Imamo matriko, katere elementi sta logični vrednosti True in False. Vrednost True pomeni, da je celica živa, vrednost False pa pomeni, da je celica mrtva. Celice (razen robnih) imajo po 8 sosedov: dva horizontalna, dve vertikalna in štiri diagonalne. Čas teče v diskretnih korakih. S trenutnim stanjem sveta je tudi stanje sveta v naslednjem koraku natanko določeno in sicer po naslednjih pravilih:

Živa celica, ki ima manj kot 2 živa soseda, umre (zaradi osamljenosti).
Živa celica, ki ima 2 ali 3 žive sosede, preživi.
Živa celica, ki ima več kot 3 žive sosede, umre (zaradi prenaseljenosti).
Mrtva celica, ki ima natanko 3 žive sosede, oživi (reprodukcija).

Primeri matrik, ki predstavljajo stanje sveta:

svet_1 = [
    [False, False, False, False, False, False],
    [False, False, False, True, False, False],
    [False, True, False, False, True, False],
    [False, True, False, False, True, False],
    [False, False, True, False, False, False],
    [False, False, False, False, False, False]
]

svet_2 = [
    [False, False, False, False],
    [False, True, True, False],
    [False, True, True, False],
    [False, False, False, False]
]

Tukaj si lahko ogledate simulacijo

1. podnaloga

Napišite funkcijo zivi(svet, i, j), ki v svetu svet prešteje in vrne število živih sosedov celice v $i$-ti vrstici in $j$-tem stolpcu. Zgled (naj bo svet_1 matrika, kot je definirana zgoraj):

>>> zivi(svet_1, 2, 0)
2

Opomba: Kot je za Python običajno, se stolpci in vrstice začnejo številčiti pri 0.

Uradna rešitev

def zivi(svet, i, j):
    '''Koliko živih sosedov ima celica (i,j) '''
    n, m = len(svet), len(svet[0]) # dimenzije sveta
    stej = 0
    for vrst in range(i-1, i+2):
        for stol in range(j-1, j+2):
            if (vrst == i) and (stol == j): # sama sebi ni sosed
                continue
            if (vrst < 0) or (vrst > n-1) or (stol < 0) or (stol > m-1):
                # smo izven sveta
                continue
            if svet[vrst][stol] : # živ sosed!
                stej += 1 
    return stej

2. podnaloga

Napišite funkcijo igra(svet), ki sestavi in vrne matriko, ki predstavlja novo stanje sveta. Štiri pravila, ki določajo novo stanje sveta, so opisana zgoraj.

Zgled (matrika svet_1 naj bo enaka kot zgoraj):

>>> igra(svet_1)
[[False, False, False, False, False, False],
 [False, False, False, False, False, False],
 [False, False, True, True, True, False],
 [False, True, True, True, False, False],
 [False, False, False, False, False, False],
 [False, False, False, False, False, False]]

Uradna rešitev

def igra(svet):
    '''vrne nov svet po enem koraku'''
    n, m = len(svet), len(svet[0])
    novSvet = []
    for i in range(n): # po vrsticah
        novaVr = []
        for j in range(m): # po stolpcih
            novaVr.append(zivi(svet, i, j) == 3 or # celica ima tri žive sosede
                           (zivi(svet, i, j) == 2 and svet[i][j])) # ali pa 2 in je ona živa
        novSvet.append(novaVr)
    return novSvet
    
## Z nekaj več znanja lahko napišemo le
##     n, m = len(svet), len(svet[0])    
##     return [[zivi(svet, i, j) == 3 or \
##        (zivi(svet, i, j) == 2 and svet[i][j]) for j in range(m)] for i in range(n)]

3. podnaloga

Napišite funkcijo populacija(svet, n), ki naredi n korakov igre življenje in na vsakem koraku prešteje število živih celic. Ta števila naj vrne v obliki seznama, ki ima $n + 1$ elementov – prvo število v seznamu naj bo število živih celic v začetnem svetu. Zgled (matrika svet_1 naj bo enaka kot zgoraj):

>>> populacija(svet_1, 3)
[6, 6, 6, 6]

Funkcijo bomo testirali še na naslednjih svetovih (poleg tistih dveh, ki sta podana zgoraj):

svet_3 = [
    [False, False, False, False, False, False],
    [False, True, True, False, False, False],
    [False, True, True, False, False, False],
    [False, False, False, True, True, False],
    [False, False, False, True, True, False],
    [False, False, False, False, False, False]
]

svet_4 = [
    [True, True, True],
    [True, True, True],
    [True, True, True]
]

Nasvet: Najprej napišite pomožno funkcijo, ki prešteje število živih celic v matriki.

Uradna rešitev

def kolikoŽivih(svet):
    '''Koliko je v svetu živih celic'''
    n, m = len(svet), len(svet[0])
    koliko = 0
    for i in range(n): # po vrsticah
        novaVr = []
        for j in range(m): # po stolpcih
            if svet[i][j] : # živa celica!
                koliko += 1
    return koliko


def populacija(svet, n):
    '''Kako se v n korakih spreminja populacija živih celic'''
    ret = [kolikoŽivih(svet)] # stanje na začetku
    for i in range(n): # koliko korakov
        svet = igra(svet) # nov svet
        ret.append(kolikoŽivih(svet)) # dodamo število živih
    return ret

## Z nekaj več znanja:
##
## def kolikoŽivih(svet):
##    return sum(sum(1 if x else 0 for x in vr) for vr in svet)
##
## def populacija(svet, n):
##    ret = [pop(svet)]
##    for i in range(n):
##        svet = igra(svet)
##        ret.append(kolikoŽivih(svet))
##    return ret

Analiza besedila

Pri tej nalogi bomo analizirali nize, ki predstavljajo pravilno slovensko oblikovane besede in stavke. Pri vseh podnaloge lahko predpostavite, da so vhodni nizi s dobro oblikovani, tj. ne vsebujejo dveh zaporednih presledkov oz. nepotrebnih presledkov ter prelomov vrstice na začetku ali na koncu.

1. podnaloga

Sestavite funkcijo stevilo_besed(s), ki v podanem nizu prešteje število besed, pri čemer lahko predpostavite, da presledki stojijo natanko pred vsako (razen prvo) besedo v nizu. Primer:

>>> stevilo_besed('Višje, hitreje, močneje!')
3

Uradna rešitev

def stevilo_besed(s):
    '''Koliko besed je v nizu s'''
    if s == '':
        return 0
    return s.count(' ') + 1 # +1 zaradi prve besede

2. podnaloga

Sestavite funkcijo samoglasniki(s), ki v podanem nizu s prešteje število samoglasnikov. Zgled:

>>> samoglasniki('pomaranča')
4

Uradna rešitev

def samoglasniki(s):
    '''Koliko je v nizu s samoglasnikov'''
    vsiSamoglasniki = 'aeiouAEIOU'
    stevec = 0
    for c in s:
        if c in vsiSamoglasniki:
            stevec += 1
    return stevec

3. podnaloga

V Pythonu vrstice večvrstičnega niza ločujemo z znakom '\n'. Sestavite funkcijo vrstice(s), ki sprejme večvrstični niz s in vrne seznam, ki vsebuje vse vrstice tega niza (v istem vrstnem redu). Zgled:

>>> vrstice("Danes\n je lep\ndan.\n")
['Danes', ' je lep', 'dan.', '']

Opomba: Python obravnava niz '\n' kot en sam znak.

Uradna rešitev

def vrstice(s):
    '''Vrne seznam vrstic v nizu s'''
    return s.split('\n')

4. podnaloga

Haiku (japonsko 俳句) je japonska pesniška oblika iz treh verzov (vrstic), ki obsega sedemnajst zlogov. Prvi in tretji verz imata po pet zlogov, drugi sedem.

Na kulturnem natečaju TomoHaiku udeleženci oddajajo svoje izdelke na strežnik Tomo. Napišite kontrolno funkcijo haiku(s), ki sprejme niz s, ter vrne True, če niz ustreza pesniški obliki haiku, sicer pa vrne False.

Predpostavite lahko, da število samoglasnikov v neki besedi ustreza številu njenih zlogov, ter da niz s ne vsebuje nepotrebnih začetnih oz. končnih praznih vrstic. Vrstice so ločene z znakom za prelom vrstice '\n'. Primer:

>>> haiku('Skrit v svojem svetu,\ntemna otožnost neba,\ntvoj topli objem.')
True
>>> haiku('Riba,\nraca, rak,\nvinjak je grenak!')
False

Uradna rešitev

def haiku(s):
    '''Preveri, ali je v nizu s zapisan haiku'''
    if s.count('\n') != 2: # premalo vrstic
        return False
    i = s.find('\n') # konec prve vrstice
    j = s.find('\n', i + 1) # konec druge
    # prva in tretja morate imeti 5, srednja pa 7 samoglasnikov
    return samoglasniki(s[:i]) == samoglasniki(s[j:]) == 5 and samoglasniki(s[i:j]) == 7

5. podnaloga

Sestavite funkcijo podcrtaj(s), ki za parameter dobi niz s, v katerem so podnizi, ki bi morali biti izpisani podčrtano, označeni s podčrtajem na začetku in na koncu. Če je v nizu liho mnogo podčrtajev, si mislite, da je še eden na koncu. Funkcija naj vrne dvovrstični niz, kjer je v prvi vrstici originalni niz s toda brez podčrtajev, sledi znak za prelom vrstice, naslednjo vrstico pa sestavlja niz, sestavljen iz presledkov in minusov, pri čemer minusi ležijo pod tistimi deli besedila, ki morajo biti podčrtani. Primer:

>>> podcrtaj("Jaz _sem_ pa cajzelc!")
'Jaz sem pa cajzelc!\n    ---            '

Predpostavite, da v nizu s ni nobenega znaka '\n'.

Uradna rešitev

def podcrtaj(s):
    '''Vrne niz iz dveh vrstic, kjer so ustrezni znaki podčrtani'''
    prvaVrsta = ''
    drugaVrsta = ''
    podcrtujem = False  # ali so trenutni znaki podčrtani
    for znak in s:
        if znak == '_': # preklopimo način podčrtovanja
            podcrtujem = not podcrtujem
        else:
            prvaVrsta += znak # v prvi vrsti so vsi znaki razen podčrtajev
            if podcrtujem: # v drugi pa bodisi presledki, bodisi podčrtaji
                drugaVrsta += '-'
            else:
                drugaVrsta += ' '
    return prvaVrsta + '\n' + drugaVrsta

6. podnaloga

Sestavite funkcijo stevilo_znakov(s), ki v podanem nizu s prešteje število znakov, pri čemer se presledki ne upoštevajo. Zgled:

>>> stevilo_znakov('B     u!')
3

Uradna rešitev

def stevilo_znakov(s):
    '''Število znakov brez presledkov'''
    return len(s) - s.count(' ')

7. podnaloga

Sonet je priljubljena pesniška oblika. Sestavljen je iz štirih kitic, pri čemur med vsakima dvema kiticama avtor izpusti eno prazno vrstico. Prvi dve kitici sta štirivrstični — kvartini, drugi dve pa sta trivrstični — tercini.

V slovenskem sonetu je standardni verz italijanski (laški) ali jambski enajsterec. To pomeni, da v vsaki vrstici nastopa natanko enajst zlogov.

Na kulturnem natečaju TomoSonet udeleženci oddajajo svoje izdelke na strežnik Tomo. Napiši kontrolno funkcijo sonet(s), ki sprejme niz s, ter vrne True, če niz ustreza slovenskemu sonetu, in False sicer. Zgled:

>>> sonet('Bolj slab\nsonet.\n\nZa umret!')
False

Namig: V slovenskem jeziku število samoglasnikov v neki besedi ustreza številu njenih zlogov. (Obstaja nekaj izjem, ki pa jih bomo zanemarili.)

Uradna rešitev

def sonet(s):
    '''Ali je v s zapisan sonet'''
    v = vrstice(s) # seznam vrstic - s pomočjo funkcije od prej!
    if len(v) != 17:
        return False  # Sonet mora imeti 14 + 3 (prazne) = 17 vrstic.
    for i in range(17): # indeksi vseh vrstic
        if i in [4, 9, 13]:
            if v[i] != '':
                return False  # Med kiticami morajo biti prazne vrstice.
        else:
            if samoglasniki(v[i]) != 11:
                return False  # Verz ni jambski enajsterec.
    return True

Lepšanje in šifriranje

1. podnaloga

Klodovik /papiga/ in ne Klodvik, frankofonski kralj/ bi rad zašifriral svoja besedila, da jih nepoklicane osebe ne bodo mogle prebrati. To stori tako, da najprej v besedilu vse male črke spremeni v velike in odstrani vse znaki, ki niso črke. (Klodvik vsa pomembna besedila piše v angleščini. Uporabljali bomo angleško abecedo.) Na primer iz besedila 'Attack at dawn!' dobi besedilo 'ATTACKATDAWN'. Nato ga zapiše cik-cak v treh vrsticah, kot prikazuje primer:

A...C...D...
.T.A.K.T.A.N
..T...A...W.

Sestavite funkcijo cik_cak(s), ki vrne trojico nizov (torej tuple) in sicer prvo, drugo in tretjo vrstico v tem zapisu. Primer:

>>> cik_cak('Attack at dawn!')
('A...C...D...', '.T.A.K.T.A.N', '..T...A...W.')

Uradna rešitev

def cik_cak(niz):
    '''Niz spremenimo v trtvrstični zapis CikCak'''
    perioda = [0, 1, 2, 1] # kako se izmenjujejo nizi, kamor
                           # zapišemo znak: prva, druga, tretja, druga, prva, druga, tretja, druga ...
    niz = niz.upper()
    vrste = ['', '', '']  # vrstice bodo na začetku seznami, da jih lahko spreminjamo!
    stevec = 0 # kateri znak jemljemo 
    for znak in niz:
        if not 'A' <= znak <= 'Z': # če ne gre za znak angleške abecede
            continue
        pos = perioda[stevec % 4] # kam bomo napisali znak
        vrste[pos] += znak
        vrste[(pos+1)%3] += '.'
        vrste[(pos+2)%3] += '.'
        stevec += 1
    return tuple(vrste) # vrniti moramo trojico!

2. podnaloga

Zašifrirano besedilo dobi tako, da najprej prepiše vse znake iz prve vrstice, nato vse znake iz druge vrstice in na koncu še vse znake iz tretje vrstice. V zgornjem primeru bi tako dobil 'ACDTAKTANTAW'. Sestavite funkcijo cik_cak_sifra(s), ki dobi kot argument niz s in vrne zašifrirano besedilo. Primer:

>>> cik_cak_sifra('Attack at dawn!')
'ACDTAKTANTAW'

Uradna rešitev

def cik_cak_sifra(s):
    '''Zašifrirajmo besedilo'''
    prva, druga, tretja = cik_cak(s) # najprej zapišemo cik-cak
    sifra = ''
    for znak in prva + druga + tretja: # gremo preko vseh treh vrstic
        if znak != '.': # spustimo pike
            sifra += znak
    return sifra

3. podnaloga

Klodovik se zelo razjezi, ko dobi elektronsko pošto v takšni obliki:

Kar sva  si obljubljala    že leta,  si   želiva potrditi tudi   pred prijatelji in   celo
žlahto. Vabiva te na

     poročno slovesnost,        ki bo
   10.   maja 2016 ob    15.    uri na gradu Otočec.   Prijetno   druženje bomo 
nadaljevali v    hotelu   Mons.   Tjaša in  Pavle

Nepopisno mu gre na živce, da je med besedami po več presledkov. Še bolj pa ga nervira, ker so nekatere vrstice precej daljše od drugih. Ker je Klodvik vaš dober prijatelj, mu boste pomagali in napisali funkcije, s katerimi bo lahko olepšal besedila.

Najprej napišite funkcijo razrez(s), ki kot argument dobi niz s in vrne seznam besed v tem nizu. Besede so med seboj ločene z enim ali večimi praznimi znaki: ' ' (presledek), '\t' (tabulator) in '\n' (skok v novo vrstico). Pri tej nalogi ločilo obravnavamo kot del besede. Primer:

>>> razrez('   Kakšen\t pastir, \n\ntakšna  čreda. ')
['Kakšen', 'pastir,', 'takšna', 'čreda.']

Uradna rešitev

def razrez(s):
    '''Niz s razreže na podnize, ki jih ločijo "beli" presledki'''
    seznam = []
    beseda = '' # trenutna beseda, ki jo sestavljamo
    for znak in s:
        if znak in ' \n\t':  # znak ni del besede
            if len(beseda) > 0: # če je ta znak zaključil besedo, jo dodamo v seznam
                seznam.append(beseda)
            beseda = '' # in nato bomo začeli sestavljati novo
        else:
            beseda += znak # smo "znotraj" besede
    if len(beseda) > 0: # ne pozabimo na morebitno besedo na koncu!
        seznam.append(beseda)
    return seznam

4. podnaloga

Sedaj, ko že imate funkcijo razrez(s), bo lažje napisati tisto funckijo, ki jo Klodovik zares potrebuje. To je funkcija olepsanoBesedilo(s, sir), ki kot argumenta dobi niz s in naravno število sir. Funkcija vrne olepšano besedilo, kar pomeni naslednje:

Funkcija naj odstrani odvečne prazne znake.
Vsaka vrstica naj bo kar se le da dolga.
Nobena vrstica naj ne vsebuje več kot sir znakov (pri čemer znaka '\n' na koncu vrstice ne štejemo).
Besede znotraj iste vrstice naj bodo ločene s po enim presledkom (ne glede na to s katerimi in koliko praznimi znaki so ločene v originalnem besedilu).

Predpostavite, da dolžina nobene besede ni več kot sir in da je niz s neprazen. Primer:

>>> s2 = olepsanoBesedilo('  Jasno in   svetlo \t\tna sveti \t\n\nvečer,  dobre\t\t letine je dost, če pa je\t  oblačno in   temno,        žita ne bo.', 20)
>>> print(s2)
Jasno in svetlo na
sveti večer, dobre
letine je dost, če
pa je oblačno in
temno, žita ne bo.

Uradna rešitev

def olepsanoBesedilo(s, sir):
    '''olepša besedilo do največje širine sir'''
    besedilo = '' #končno besedilo
    besede = razrez(s) # razrežemo na posamezne besede
    vrstica = ''
    for b in besede:
        if len(vrstica) + len(b) > sir: # če je beseda, ki je na vrsti, predolga
            besedilo += vrstica[:-1] + '\n' # odrežemo presledek, ki smo ga dodali za stikanje
            vrstica = '' # začnemo novo vrstico
        vrstica += b + ' '
    if len(vrstica) > 0: # ne pozabimo na zadnjo vrstico!
        besedilo += vrstica[:-1] + '\n'
    return besedilo[:-1] # na koncu je odvečni prehod v novo vrsto

Malica

Srednje šole po Sloveniji si prizadevajo, da bi njihovi dijaki jedli čim bolj zdravo malico. Ravnatelj ene od srednjih šol je vaš dobri prijatelj. Rad bi, da mu napišete program, s katerim bo lahko analiziral jedilnike, saj si želi, da bi bili njegovi dijaki zdravi in srečni.

   primer_jedilnika = [
       'svinjski zrezek v omaki', 'sirov kanelon', 'ocvrt oslič',
       'svinjski zrezek v omaki', 'ocvrt oslič', 'sirov burek',
       'sirov kanelon', 'ocvrt oslič', 'sirov kanelon', 'sirov kanelon'

1. podnaloga

Jedilnik opišemo s seznamom nizov, kot vidite na primeru. Vsak zaporedni element seznama ustreza enemu od zaporednih dni. Jedilnik se periodično ponavlja. Če je dolžina jedilnika $n$, bodo dijaki $(n+1)$-ti dan spet jedli tisto, kar je na prvem mestu na jedilniku. Ravnatelj je opazil, da so nekatere stvari na jedilniku napisane po večkrat. Rad bi, da napišete funkcijo brez_ponovitev(l), ki sestavi nov seznam, tako da se bo vsak element pojavil samo enkrat. Zgled:

>>> brez_ponovitev(primer_jedilnika)
['svinjski zrezek v omaki', 'sirov kanelon', 'ocvrt oslič', 'sirov burek']

Elementi naj se v novem seznamu pojavijo v takem vrstnem redu, kot njihove prve ponovitve v originalnem seznamu l.

Uradna rešitev

def brez_ponovitev(jedilnik):
    '''sestavi jedilnik brez ponovitev'''
    novJedilnik = []
    for jed in jedilnik:
        if jed not in novJedilnik: # če jed še ni v novem jedilniku
            novJedilnik.append(jed)
    return novJedilnik

2. podnaloga

Ravnatelj je sicer ugotovil, da se jedi ponavljajo. Če pa je od dneva, ko je bila neka jed nazadnje na jedilniku, minilo dovolj časa, ni s tem nič narobe. Napišite funkcijo kdaj_prej(l), ki dobi nek jedilnik in vrne enako dolg seznam, kjer je za vsak dan ena številka in sicer koliko dni je minilo od takrat, ko je bila jed nazadnje na jedilniku. Upoštevajte, da je jedilnik periodičen, torej jedilnik ['burek', 'jogurt', 'burek'] je v 5 dneh ['burek', 'jogurt', 'burek', 'burek', 'jogurt'] v 10 pa ['burek', 'jogurt', 'burek', 'burek', 'jogurt', 'burek', 'burek', 'jogurt', 'burek', 'burek'] Primer:

>>> kdaj_prej(['burek', 'jogurt', 'burek'])
[1, 3, 2]
>>> kdaj_prej(primer_jedilnika)
[7, 2, 5, 3, 2, 10, 5, 3, 2, 1]

Uradna rešitev

def kdaj_prej(jedilnik):
    '''Koliko dni je minilo pred enako jednjo'''
    ustrezniIndeksi = []
    n = len(jedilnik)
    for dan in range(n):
        j = dan - 1 # dan prej 
        jedTaDan = jedilnik[dan]
        while jedilnik[j%n] != jedTaDan: #kdaj je bila ta jed prej
            j -= 1 
        ustrezniIndeksi.append(dan - j)
    return ustrezniIndeksi

3. podnaloga

Ravnatelj je definiral pojma raznolikost in kakovost. (Opomba: Ravnatelj je študiral matematiko in jo svoje čase tudi poučeval.) Raznolikost je število različnih jedi na jedilniku. Kakovost pa je povprečje kvadratov vrednosti elementov seznama, ki ga vrne funkcija kdaj_prej(l). Sestavite funkcijo raznolikost_in_kakovost(l), ki vrne par števil in sicer raznolikost in kakovost jedilnika l. Primer:

>>> raznolikost_in_kakovost(['burek', 'burek', 'jogurt'])
(2, 4.666666666666667)
>>> raznolikost_in_kakovost(primer_jedilnika)
(4, 23.0)

Uradna rešitev

def raznolikost_in_kakovost(jedilnik):
    '''Vrne raznolikost in kakovost jedilnika'''
    jedilnikBP = brez_ponovitev(jedilnik) # število različnih jedi bo raznolikost!
    kdajPrej = kdaj_prej(jedilnik) # koliko nazaj je bila posamezna jed
    vsotaKv = 0
    for kolikoNazaj in kdajPrej:
        vsotaKv += kolikoNazaj**2
    povp = vsotaKv / len(kdajPrej)
    return len(jedilnikBP), povp

4. podnaloga

Ravnatelj je v zbornici zbral različne predloge jedilnikov in jih združil v en sam seznam. Sestavite funkcijo naj_jedilnik(ll), ki izmed vseh teh jedilnikov v seznamu ll izbere in vrne najboljšega. Bolši je tisti jedilnik, ki je bolj raznolik. Med jedilniki z enako raznolikostjo je boljši tisti, ki je kakovostnejši. Predpostavite, da imate vsaj en jedilnik in da v podatkih ne bo dveh enako dobrih jedilnikov. Primer:

>>> naj_jedilnik([['burek', 'jogurt'], ['pomaranča', 'pomaranča']])
['burek', 'jogurt']

>>> naj_jedilnik([['burek', 'jogurt'], primer_jedilnika])
['svinjski zrezek v omaki', 'sirov kanelon', 'ocvrt oslič',
'svinjski zrezek v omaki', 'ocvrt oslič', 'sirov burek',
'sirov kanelon', 'ocvrt oslič', 'sirov kanelon', 'sirov kanelon']

Uradna rešitev

def naj_jedilnik(seznamJedilnikov):
    '''Iz seznama jedilnikov poiščemo najboljšega'''
    naj = seznamJedilnikov[0] # kandidat za najboljšega je prvi 
    for jedilnik in seznamJedilnikov[1:]: # pregledamo še ostale
        if raznolikost_in_kakovost(jedilnik) > raznolikost_in_kakovost(naj): # pari se primerjajo "leksikografsko"
            naj = jedilnik
    return naj

FizzBuzz

FizzBuzz je priljubljena otroška igrica, ki se jo lahko igrajo vsi otroci, ki znajo deliti cela števila. Otroci se usedejo v krog in štejejo (začenši z 1), pri čemer številke glasno izgovarjajo. Če je število deljivo s 3, potem morajo (namesto številke) zaklicati ‘Fizz!’. Če je število deljivo s 5, morajo zaklicati ‘Buzz!’. Če pa je število deljivo s 3 in 5 hkrati, morajo zaklicati ‘Fizzbuzz!’.

1. podnaloga

Sestavite funkcijo fizzbuzz(n), ki kot argument dobi naravno število n in vrne seznam števil od 1 do $n$, pri čemer naj:

večkratnike števila 3 zamenja z nizom 'Fizz',
večkratnike števila 5 zamenja z nizom 'Buzz',
večkratnike števila 15 pa zamenja z nizom 'FizzBuzz'.

Primer:

   >>> fizzbuzz(16)
   [1, 2, 'Fizz', 4, 'Buzz', 'Fizz', 7, 8, 'Fizz', 'Buzz', 11, 'Fizz', 13, 14, 'FizzBuzz', 16]

Uradna rešitev

def fb(n):
    '''Kaj naj pove, če je na vrsti n'''
    if n % 15 == 0: # večkratnik 15 moramo preveriti prvega!
        return 'FizzBuzz'
    if n % 3 == 0:
        return 'Fizz'
    if n % 5 == 0:
        return 'Buzz'
    return n

def fizzbuzz(n):
    '''Vrne seznam ustreznih besed za igro Fizz buzz, če števejo do n'''
    seznamBesed = []
    for i in range(1, n+1):
        seznamBesed.append(fb(i))
    return seznamBesed

2. podnaloga

Sestavite še funkcijo poisci_napake(l), ki kot argument prejme seznam l. Ta seznam je FizzBuzz zaporedje, ki lahko vsebuje napake. Funkcija naj vrne seznam vseh indeksov seznama l, kjer se pojavijo napake. Elementi izhodnega seznama naj bodo urejeni naraščajoče. Zgled:

>>> poisci_napake([1, 2, 3, 'Fizz', 'Buzz', 7, 'Fizz', 8])
[2, 3, 5, 6]

Uradna rešitev

def poisci_napake(l):
    '''Poiščemo indekse, kjer je v seznamu l, napaka za igro FizzBuzzz'''
    napake = []
    pravilno = fizzbuzz(len(l))
    for i in range(len(l)):
        if l[i] != pravilno[i]:
            napake.append(i)
    return napake